Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Influence maximization algorithm based on node coverage and structural hole
Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG
Journal of Computer Applications    2022, 42 (4): 1155-1161.   DOI: 10.11772/j.issn.1001-9081.2021071256
Abstract279)   HTML6)    PDF (829KB)(108)       Save

Influence maximization is one of the important issues in social network analysis, which aims to identify a small group of seed nodes. When these nodes act as initial spreaders, information can be spread to the remaining nodes as much as possible in the network. The existing heuristic algorithms based on network topology usually only consider one single network centrality, failing to comprehensively combine node characteristics and network topology; thus, their performance is unstable and can be easily affected by the network structure. To solve the above problem, an influence maximization algorithm based on Node Coverage and Structural Hole (NCSH) was proposed. Firstly, the coverages and grid constraint coefficients of all nodes were calculated. Then the seed was selected according to the principle of maximum coverage gain. Secondly, if there were multiple nodes with the same gain, the seed was selected according to the principle of minimum grid constraint coefficient. Finally, the above steps were performed repeatedly until all seeds were selected. The proposed NCSH maintains good performance on six real networks under different numbers of seeds and different spreading probabilities. NCSH achieves 3.8% higher node coverage than to the similar NCA (Node Coverage Algorithm) on average, and 43% lower time consumption than the similar SHDD (maximization algorithm based on Structure Hole and DegreeDiscount). The experimental results show that the NCSH can effectively solve the problem of influence maximization.

Table and Figures | Reference | Related Articles | Metrics